package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname RecoverTree_0099
 * @Author happytaohaha
 * @Date 2020/3/23
 * @Description 恢复树
 * 先中序排序   因为只有两个节点交换了，找到这两个节点并交换回来即可
 * 时间复杂度：O(N)。中序遍历需要O(N) 的时间，判断两个交换节点：在最好的情况下是 O(1)，在最坏的情况下是 O(N)。
空间复杂度：O(N)，我们用 nums 数组保存了树的中序遍历列表。

 */
public class RecoverTree_0099 {


    public void inOrder(TreeNode root,List<Integer> nums) {
        if (root == null) {return;}
        inOrder(root.left,nums);
        nums.add(root.val);
        inOrder(root.right,nums);
    }

    public int[] findTwoSwap(List<Integer> nums) {
        int x = -1, y = -1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i + 1) < nums.get(i)) {
                y = nums.get(i + 1);
                if (x == -1) {
                    x = nums.get(i);
                } else {
                    break;
                }
            }

        }
        return new int[]{x, y};
    }

    /**
     * 交换x,y
     * @param root
     * @param count
     * @param x
     * @param y
     */
    public void recover(TreeNode root, int count, int x, int y) {
        if (root != null) {
            if (root.val == x || root.val == y) {
                root.val = root.val == x ? y : x;
                if (--count == 0) {
                    return;
                }
            }
            recover(root.left, count, x, y);
            recover(root.right, count, x, y);
        }
    }


    public void recoverTree(TreeNode root) {
        List<Integer> nums = new ArrayList<Integer>();
        inOrder(root,nums);
        int[] swapped = findTwoSwap(nums);
        recover(root, 2, swapped[0], swapped[1]);
    }



        TreeNode x = null, y = null, pred = null;

        public void swap(TreeNode a, TreeNode b) {
            int tmp = a.val;
            a.val = b.val;
            b.val = tmp;
        }

        public void findTwoSwapped(TreeNode root) {
            if (root == null) {return;}
            findTwoSwapped(root.left);
            if (pred != null && root.val < pred.val) {
                y = root;
                if (x == null) {x = pred;}
                else {return;}
            }
            pred = root;
            findTwoSwapped(root.right);
        }

    /**
     * 递归中序遍历很简单：遵循 Left->Node->Right 方向，即对左子节点进行递归调用，然后判断该节点是否被交换，然后对右子节点执行递归调用。
     * 时间复杂度：最好的情况下是 O(1)；最坏的情况下是交换节点之一是最右边的叶节点时，此时是O(N)。
     * 空间复杂度：最大是O(H) 来维持递归调用堆栈的大小，其中 HH 指的是树的高度。
     * @param root
     */
    public void recoverTree_002(TreeNode root) {
            findTwoSwapped(root);
            swap(x, y);
        }

}
